package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/23 上午8:39
 */
public class 有效括号组合 {

    public static void main(String[] args) {

        List<String> list = generateParenthesis(1);

        System.out.println(list);

    }


    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        dfs(n,n,"",res);
        return res;
    }

    // 递归遍历所有可能，
    // 由于必须是有效的括号，那么递归过程中，剩余右括号的数量一定要大于左括号的数量
    // 否则，这种情况就是无效的，直接return；
    public static void dfs(int left,int right,String curStr,List<String> res){
        // 递归结束
        if(left == 0 && right == 0){
            res.add(curStr);
        }
        // 剩余左括号数量 > 右
        if(left > right){
            return;
        }

        // +)
        if(right > 0){
            dfs(left,right - 1,curStr + ")",res);
        }
        // +(
        if (left > 0){
            dfs(left - 1,right,curStr + "(",res);
        }
    }

}
